#include "mythread.h"
#include <QElapsedTimer>
#include <QDebug>
#include <QVector>
// renew

// 子线程
// 构造
Generate::Generate(QObject *parent) : QThread(parent)
{}

void Generate::recvNum(int num)
{
    _num = num;
}

void Generate::run()
{
    qDebug() << "生成随机数的线程，其地址: " << QThread::currentThread();
    QVector<int> qv;
    QElapsedTimer timer;
    timer.start(); // 开始计时

    for(int i = 0; i < _num; ++i)
    {
        qv.push_back(qrand() % 100000); // 随机生成_num个范围在0-100000的数字
    }

    int ms = timer.elapsed(); // 获取执行到此时间
    qDebug() << "生成" << _num << "个数字共用了" << ms << "毫秒";

    emit sendVector(qv);
}

// --------------冒泡排序-----------------
BubbleSort::BubbleSort(QObject *parent) : QThread(parent)
{}

void BubbleSort::recvVector(QVector<int> qv)
{
    _qv = qv; // 获取序列
}

void BubbleSort::run()
{
    qDebug() << "进行冒泡排序的线程，其地址 " << QThread::currentThread();
    QElapsedTimer timer;
    timer.start(); // 开始计时

    // 冒泡排序执行
    int n = _qv.size();
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n - i - 1; ++j)
        {
            if(_qv[j] > _qv[j+1])
                qSwap(_qv[j], _qv[j+1]);
        }
    }

    int ms = timer.elapsed(); // 获取执行到此时间
    qDebug() << "执行冒泡排序过程共用了" << ms << "毫秒";

    emit finish(_qv);
}


// --------------快速排序-----------------

// 构造
QuickSort::QuickSort(QObject *parent): QThread(parent)
{}

void QuickSort::recvVector(QVector<int> qv)
{
    _qv = qv;
}

void QuickSort::run()
{
    qDebug() << "进行快速排序的线程，其地址 " << QThread::currentThread();
    QElapsedTimer timer;
    timer.start(); // 开始计时

    // 快速排序执行
    QuickSort::quickSort(_qv, 0, _qv.size()-1);

    int ms = timer.elapsed(); // 获取执行到此时间
    qDebug() << "执行冒泡排序过程共用了" << ms << "毫秒";

    emit finish(_qv);
}

// 快排实现
void QuickSort::quickSort(QVector<int> &qv, int begin, int end)
{
    if (begin < end)
    {
        int i = begin, j = end;
        // 拿出第一个元素, 保存到x中,第一个位置成为一个坑
        int x = qv[begin];
        while (i < j)
        {
            // 从右向左找小于x的数
            while (i < j && qv[j] >= x)
            {
                //左移, 直到遇到小于等于x的数
                j--;
            }
            if (i < j)
            {
                //将右侧找到的小于x的元素放入左侧坑中, 右侧出现一个坑
                //左侧元素索引后移
                qv[i++] = qv[j];
            }

            // 从左向右找大于等于x的数
            while (i < j && qv[i] < x)
            {
                //右移, 直到遇到大于x的数
                i++;
            }
            if (i < j)
            {
                //将左侧找到的元素放入右侧坑中, 左侧出现一个坑
                //右侧元素索引向前移动
                qv[j--] = qv[i];
            }
        }
        //此时 i=j,将保存在x中的数填入坑中
        qv[i] = x;
        quickSort(qv, begin, i - 1); // 递归调用
        quickSort(qv, i + 1, end);
    }
}
